Introduction

In practice, it is easier to construct hashing algorithms which operate on relatively small, fixed input lengths, whilst still keeping the output length even smaller ( $l_{out}$ is still less than $l_{in}$ ). But hash functions are usually used on much larger inputs - for example, creating checksums for integrity verification of files. The Merkle-Damgård transform allows us to turn such a hash function, which operates on small fixed input lengths, into a hash function which operates on inputs of arbitrary lengths.

The Merkle-Damgård Construction

In particular, given a compression function $H^{'} (input : str [const l_{in}]) \to str [const l]$ which works with inputs of a "small", fixed input length $l_{in}$ and has outputs with length $l$ , the Merkle-Damgård transform allows us to use $H^{'}$ to a construct a hash function $H (input : str [l_{m}]) \to str [const l]$ which takes messages of arbitrary length, denoted by $l_{m}$ , and produces digests of the same output length $l$ as $H^{'}$ .

The construction is similar to a block cipher in the sense that the message $m$ is chopped up into blocks. In contrast to block ciphers, however, this is done rather differently. Each block has length $l_{in}$ (since each block will be input into $H^{'}$ ), but it is not comprised entirely of message bits. Instead, each block contains $l_{mb}$ message bits and the other $l_{t}$ bits ( $l_{t} = l_{in} - l_{mb}$ ) represent the so-called chaining variable for the current block.

This means that the message $m$ needs to be chopped up into $q$ message fragments $μ_{1}, μ_{2}, ..., μ_{q}$ , all of length $l_{mb}$ . If the message length $l_{m}$ is not a multiple of $l_{mb}$ , then the message is padded by appending a 1 to it and then appending 0s until the message length is short of a multiple of the fragment length $l_{mb}$ by exactly the number of bits $l_{e}$ needed to encode the message length $l_{m}$ . The total length of the padding (including the 1, the 0s and the encoding of the message length) is denoted by $l_{pad} = 1 + count (0) + l_{e}$ .

When the message length $l_{m}$ is a multiple of the fragment length $l_{mb}$ , padding still needs to be added. In a particular, an additional padding block is appended to the message, following the exact same procedure as before. The padding block begins with a $1$ and is followed by $0$ s - the last $l_{e}$ bits of the padding block again encode the message length $l_{m}$ .

Note

The number of bits reserved for encoding the message length $l_{mb}$ is fixed for a given Merkle-Damgård construction. Usually $l_{e}$ is 64 bits, resulting in a maximum message length of $2^{64} - 1$ , which is quite a reasonable limit.

After padding, the actual hash algorithm begins by appending an initialisation vector (IV) of length $l$ to the first message fragment $μ_{1}$ . The IV is always a constant which is pre-defined in the specification of the Merkle-Damgård construction.

Example

The SHA256 hash function uses the following 256-bit IV (the value is in hex):

$I V := 0x6A09E667BB67AE853C6EF372A54FF53A510E527F9B05688C1F83D9AB5BE0CD19$

This initialisation vector serves as the initial chaining variable $t_{1}$ . The concatenation $μ_{1} ∣∣ I V$ of the first message block $μ_{1}$ with the IV is passed to the compression function $H^{'}$ , whose output becomes the next chaining variable. In general, the $i$ -th iteration takes the $i$ -th message block $μ_{i}$ and appends to it the chaining variable $t_{i}$ . The chaining variable $t_{i}$ for the current stage is simply the output of $H^{'}$ from the previous iteration. The final output, i.e. the hash generated by the Merkle-Damgård function $H$ , is the final chaining variable.

Security of Merkle-Damgård Constructions

The reason why the Merkle-Damgård transform is used ubiquitously is the fact that it preserves collision resistance.

Theorem: Merkle-Damgård Collision Resistance

If the compression function $H^{'}$ is collision resistant, then so is the Merkle-Damgård function $H$ .

Proof: Merkle-Damgård Collision Resistance

Suppose, towards contradiction that there is an efficient collision finder $A$ which can find a collision in $H$ with non-negligible probability. Let $x$ and $x^{'}$ be two inputs of lengths $L$ and $L^{'}$ , respectively, such that $H (x) = H (x^{'})$ . Let $x_{1}, x_{2}, ..., x_{q}$ be the $q$ blocks which $x$ is divided into, and, let $x_{1}^{'}, x_{2}^{'}, ..., x_{q^{'}}^{'}$ be the $q^{'}$ blocks which $x^{'}$ is divided into. Similarly, let $t_{1}, t_{2}, ..., t_{q}, t_{q + 1}$ and $t_{1}^{'}, t_{2}^{'}, ..., t_{q^{'}}^{'}, t_{q^{'} + 1}^{'}$ be the chaining variables used at each iteration of the hashing of $x$ and $x^{'}$ , respectively (remember that the chaining variables $t_{q + 1}$ and $t_{q^{'} + 1}^{'}$ are also the output of $H$ ).

Case 1: If the two inputs have different lengths, i.e. $L \neq = L^{'}$ , then the hash $H (x)$ is $t_{q + 1} : = H^{'} (x_{q} ∣∣ t_{q})$ and the hash $H (x^{'})$ is $t_{q^{'} + 1}^{'} : = H^{'} (x_{q}^{'} ∣∣ t_{q^{'}}^{'})$ . However, $H (x) = H (x^{'})$ means that $H^{'} (x_{q} ∣∣ t_{q}) = H^{'} (x_{q}^{'} ∣∣ t_{q^{'}}^{'})$ which is a contradiction because $L \neq = L^{'}$ and so $x_{q} \neq = x_{q^{'}}^{'}$ (remember that the length is appended to the message when padding) - we have found two different inputs which cause a collision in the collision resistant $H^{'}$ .

Case 2: If the two inputs have the same length, i.e. $L = L^{'}$ , then they are also divided into the same number of blocks $q = q^{'}$ . Let $I_{i} : = x_{i} ∣∣ t_{i}$ denote the $i$ -th input passed to $H^{'}$ when computing $H (x)$ , and let $I_{i}^{'} : = x_{i}^{'} ∣∣ t_{i}^{'}$ denote the $i$ -th input passed to $H^{'}$ when computing $H (x^{'})$ . Additionally, we will denote the output of $H (x)$ as $I_{q + 1} : = t_{q + 1}$ , and we will denote the output of $H (x^{'})$ as $I_{q^{'} + 1}^{'} : = t_{q^{'} + 1}^{'}$ .

Now, $H (x) = H (x^{'})$ and so $I_{q + 1} = t_{q + 1} = I_{q^{'} + 1}^{'} = t_{q^{'} + 1}^{'}$ . This can only happen if $I_{q} = I_{q^{'}}^{'}$ or if $(I_{q}, I_{q^{'}}^{'})$ is a collision pair for $H^{'}$ and the same logic propagates backwards - in general, $H^{'} (I_{i}) = H^{'} (I_{i}^{'})$ can be true only if $I_{i} = I_{i}^{'}$ or if $(I_{i}, I_{i^{'}}^{'})$ is a collision pair for $H^{'}$ . The inputs $x, x^{'}$ are a collision pair for $H$ which means that $x \neq = x^{'}$ and so there must be some index $j$ for which $x_{j} \neq = x_{j}^{'}$ which means for sure that $I_{j} \neq = I_{j}^{'}$ and so $(I_{j}, I_{j}^{'})$ turn out to be a collision in $H^{'}$ , which is a contradiction.

The Cyberclopaedia

Introduction

The Merkle-Damgård Construction

Security of Merkle-Damgård Constructions